package com.trajan.exercise.datastructure;

/*

   Created with IntelliJ IDEA.

   Ing. Tomáš Herich
   --------------------------- 
   12. 06. 2013
   7:12 PM

*/

public class BinaryTree {

    public static Node root;
    public int level = 0;

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();

        tree.addNode(50, "1");
        tree.addNode(25, "2");
        tree.addNode(15, "3");
        tree.addNode(30, "4");
        tree.addNode(35, "5");
        tree.addNode(10, "6");
        tree.addNode(70, "7");
        tree.addNode(85, "8");
        tree.addNode(75, "9");
        tree.addNode(90, "10");

        System.out.println("\n\nIn order traversal\n");
        tree.inOrderTraversal(root);

        System.out.println("\n\nReverse order traversal\n");
        tree.reverseOrderTraversal(root);

        System.out.println("\n\nPre order traversal\n");
        tree.preOrderTraversal(root);

        System.out.println("\n\nPost order traversal\n");
        tree.postOrderTraversal(root);

        tree.findNode(10);
    }


    public Node findNode(int key) {

        Node focusNode = root;

        while (focusNode.getKey() != key) {

            if (key < focusNode.getKey()) {
                focusNode = focusNode.getLeftNode();
            } else {
                focusNode = focusNode.getRightNode();
            }

            if (focusNode == null) {
                return null;
            }
        }

        System.out.println("\nFound node: " + focusNode.toString());

        return focusNode;

    }

    public void postOrderTraversal(Node focusNode) {

        if (focusNode != null) {

            postOrderTraversal(focusNode.getLeftNode());

            postOrderTraversal(focusNode.getRightNode());

            System.out.println(focusNode.toString());

        }

    }

    public void preOrderTraversal(Node focusNode) {

        if (focusNode != null) {

            System.out.println(focusNode.toString());

            preOrderTraversal(focusNode.getLeftNode());

            preOrderTraversal(focusNode.getRightNode());

        }
    }

    public void inOrderTraversal(Node focusNode) {

        if (focusNode != null) {

            inOrderTraversal(focusNode.getLeftNode());

            System.out.println(focusNode.toString());

            inOrderTraversal(focusNode.getRightNode());

        }
    }

    public void reverseOrderTraversal(Node focusNode) {

        if (focusNode != null) {

            reverseOrderTraversal(focusNode.getRightNode());

            System.out.println(focusNode.toString());

            reverseOrderTraversal(focusNode.getLeftNode());

        }
    }


    public void addNode(int key, String name) {

        Node newNode = new Node(key, name);

        if (root == null) {
            root = newNode;
        } else {

            Node focusNode = root;

            Node parent;

            while (true) {

                parent = focusNode;

                if (key < focusNode.getKey()) {

                    focusNode = focusNode.getLeftNode();

                    if (focusNode == null) {

                        parent.setLeftNode(newNode);
                        return;
                    }

                } else {

                    focusNode = focusNode.getRightNode();

                    if (focusNode == null) {

                        parent.setRightNode(newNode);
                        return;

                    }
                }
            }
        }
    }

    private class Node {

        private int key;
        private String name;

        private Node leftNode;
        private Node rightNode;

        Node(int key, String name) {
            this.key = key;
            this.name = name;
        }

        @Override
        public String toString() {
            return name + " has a key " + key;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Node getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        public Node getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }
    }

}


